\section{A Serial Implementation Using Binning}
\label{sec:serial}

A naive implementation of particle simulation requires $O(n^2)$ to run because at each time step, the pairwise force between all particles is calculated; \texttt{apply\_force(p\_i, p\_j)} is called for all \texttt{i, j}.  However, any given particle is only influenced by the force of its local {\it i.e.}, neighboring particles, so when this function is called, force is only actually applied between particles that are within a cutoff distance of each other. Thus, it should only be necessary to call \texttt{apply\_force(p\_i, p\_j)} when \texttt{p\_i} and \texttt{p\_j} are local to one another. In this assignment, we can assume that the number of local interactions is $O(n)$. Thus, to reduce the runtime to $O(n)$ adjust the implementation so that \texttt{apply\_force} is only called $O(n)$ times.

To do this we use a binning approach on the GPU, guided by a serial implementation which also uses the binning approach, listed in the appendix.  This serial implementation partitions the grid of particles into square ``bins'', or sub-grids, with a size equal to the local interaction cutoff.  This size guarantees that any given particle will only interact with particles in its own bin or the 8 neighboring bins, which in turn results in the desired $O(n)$ running time. A high-level overview of the binning-based implementation is provided below. 

\begin{quote}
\begin{verbatim}
for each time step:
   clear_bins
   fill_bins
   compute_forces
   move_particles
\end{verbatim}
\end{quote}

The main things added to the original particle simulation implementation to achieve a binned implementation as above are (1) computing to which bin each particle belongs in \texttt{fill\_bins} and (2) deciding which particles are local in \texttt{compute\_forces} to call \texttt{apply\_force} between them.

%\begin{figure}[h!]
%\includegraphics[width=\textwidth]{./figs/quadtree.pdf}
%\caption{An example of quadtree.  The quadtree recursively divides the particle space such that each leaf has a particle.}
%\label{fig:quadtree}
%\end{figure}
